// https://leetcode.cn/problems/remove-linked-list-elements/

// 算法思路总结：
// 1. 使用虚拟头节点统一删除操作
// 2. 遍历链表，检查每个节点的下一个节点值
// 3. 遇到目标值节点时直接跳过连接
// 4. 非目标值节点时正常移动指针
// 5. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        if (head == nullptr) return nullptr;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        auto cur = dummy;
        while (cur != nullptr && cur->next != nullptr)
        {
            if (cur->next->val == val)
            {
                cur->next = cur->next->next;
            }
            else 
            {
                cur = cur->next;
            }
        }

        auto result = dummy->next;
        delete dummy;

        return result;
    }
};

int main()
{
    vector<int> nodes1 = {1,2,6,3,4,5,6};
    vector<int> nodes2 = {7,7,7,7};
    int val1 = 6, val2 = 7;

    Solution sol;
    
    auto l1 = createLinkedList(nodes1);
    auto l2 = createLinkedList(nodes2);

    auto r1 = sol.removeElements(l1, val1);
    auto r2 = sol.removeElements(l2, val2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}